package 华为OD机试真题2023.进阶题;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import utils.MyUtil;

public class HJ07_计算至少需要多少个快递主站点 {
  public static void main(String[] args) throws FileNotFoundException {
    MyUtil.START();
    Solution();
    //    Solution2();
    MyUtil.END();
  }

  static int[] visited = new int[10000];

  static void Solution() throws FileNotFoundException {
    Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/07.txt"));
    int N = in.nextInt();
    int[][] matrix = new int[N][N];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        matrix[i][j] = in.nextInt();
      }
    }
    int res = 0;
    for (int i = 0; i < N; i++) {
      if (visited[i] == 0) {
        res++;
        visited[i] = 1;
        dfs(matrix, i);
      }
    }
    System.out.println(res);
  }

  static void dfs(int[][] matrix, int index) {
    for (int i = 0; i < matrix[0].length; i++) {
      if (matrix[index][i] == 1 && visited[i] == 0) {
        visited[i] = 1;
        dfs(matrix, i);
      }
    }
  }

  static int[][] square;

  static void Solution2() throws FileNotFoundException {
    Scanner scanner = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/07.txt"));
    int num = scanner.nextInt();
    square = new int[num][num];
    int row = 0;
    int column = 0;
    while (row < num) {
      column = 0;
      while (column < num) {
        square[row][column] = scanner.nextInt();
        column++;
      }
      row++;
    }
    Set<Integer> set = new HashSet<>();
    int res = 0;
    int i = 0;
    while (i < num) {
      if (set.contains(i)) {
        i++;
        continue;
      }
      Set<Integer> temporary = new HashSet<>();
      temporary.add(i);
      trace(temporary, i);
      set.addAll(temporary);
      res++;
      i++;
    }
    System.out.println(res);
  }

  static void trace(Set<Integer> temporary, int n) {
    int i = 0;
    while (i < square.length) {
      if (temporary.contains(i)) {
        i++;
        continue;
      }
      if (n != i && square[n][i] == 1) {
        temporary.add(i);
        trace(temporary, i);
      }
      i++;
    }
  }
}
